public class MajorityElement {
    public int majorityElement(int[] nums) {
       // 处理边界情况
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }
        int count = 1;
        int candidate = nums[0];
        for(int i = 1; i< nums.length; i++){
          if (count == 0){
            count++;
            candidate = nums[i];
          } else if(nums[i] == candidate){
            count++;
          } else {
            count--;
          }
        }
        // 验证候选者是否真的是多数元素
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        if (count > nums.length / 2) {
            return candidate;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] nums = {1,2,5,9,5,9,5,5,5};
        System.out.println(new MajorityElement().majorityElement(nums));
    }
}



// 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

 

// 示例 1：

// 输入：[1,2,5,9,5,9,5,5,5]
// 输出：5
// 示例 2：

// 输入：[3,2]
// 输出：-1
// 示例 3：

// 输入：[2,2,1,1,1,2,2]
// 输出：2